package com.cet.qz.unit01.chapter1_3;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description: 双向队列
 * @author: 陈恩涛
 * @create: 2021-04-20 20:38
 **/
public class Deque<Item> implements Iterable<Item> {

    private class DoubleNode {
        private Item item;
        private DoubleNode prior;
        private DoubleNode next;
    }

    private DoubleNode first;
    private DoubleNode last;
    private int n;

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void pushLeft(Item item) {
        DoubleNode insertNode = new DoubleNode();
        insertNode.item = item;
        if (isEmpty()) {
            first = last = insertNode;
        } else {
            insertNode.next = first;
            first.prior = insertNode;
            first = insertNode;
        }
        n++;

    }

    public void pushRight(Item item) {
        DoubleNode insertNode = new DoubleNode();
        insertNode.item = item;
        if (isEmpty()) {
            first = last = insertNode;
        } else {
            insertNode.prior = last;
            last.next = insertNode;
            last = insertNode;
        }
        n++;
    }

    public Item popLeft() {

        if (isEmpty()) {
            throw new RuntimeException("Deque is null!");
        }
        Item item = first.item;
        if (size() > 1) {
            first.next.prior = null;
        } else {
            last = null;
        }
        first = first.next;
        n--;
        return item;
    }

    public Item popRight() {
        if (isEmpty()) {
            throw new RuntimeException("Deque is null!");
        }
        Item item = last.item;
        if (size() > 1) {
            last.prior.next = null;
        } else {
            first = null;
        }
        last = last.prior;
        n--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new DequeIterator(first);
    }

    class DequeIterator implements Iterator<Item> {

        private DoubleNode firstNode;

        public DequeIterator(DoubleNode firstNode) {
            this.firstNode = firstNode;
        }

        @Override
        public boolean hasNext() {
            return firstNode != null;
        }

        @Override
        public Item next() {
            Item item = firstNode.item;
            firstNode = firstNode.next;
            return item;
        }

        @Override
        public void remove() {

        }
    }

    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();
        deque.pushLeft(1);
        deque.pushRight(2);
        deque.pushLeft(3);
        deque.pushRight(4);
        for (Integer i : deque) {
            System.out.println(i);
        }

        System.out.println("=============");
        System.out.println(deque.popLeft());
        System.out.println(deque.popRight());
    }

}
